#include <cstdlib>
#include <stdlib.h>
#include <set>
#include <vector>
#include <list>
#include <ctime> 
#include <typeinfo>
#include "graph.h"
#include "RankSet.h"
#include "Vertex.h"
#include "VertexSet.h"
#include "Helpers.h"



using namespace std;

//----------------------------------------------------------------------------------------
// Public
//----------------------------------------------------------------------------------------

//----------------------------------------------------------------------------------------
// Ctor: the graph will use the specified VertexDirectory dir
//----------------------------------------------------------------------------------------
Graph::Graph(int maxCouplesForMinimalRank, int randomIterations, VertexDirectory* dir)
{
	m_MaxVertexCouplesForMininalRankSearch = maxCouplesForMinimalRank;
	m_RandomIterations = randomIterations; 
	srand((unsigned)time(0));
	try
	{
		m_TempContainer = new TempVertexContainer(this);
	}
	catch(std::bad_alloc *e)
	{
		e = NULL;
		Logger::LogMessage("failed to create a Graph object reseon: memory allocation failed.");
		throw(new GraphColoringException("memory allocation failed"));
	}

	m_Directory = dir;
}


//---------------------------------------------------------------------------------
// Dtor
//---------------------------------------------------------------------------------
Graph::~Graph()
{
	delete m_TempContainer;
	GraphVerticesIterator it;
	RemoveEmptyRankSets();
	for (it = m_Vertices.begin(); it != m_Vertices.end(); it++)
	{
		if (it->second != NULL)
		{
			delete it->second;
		}
	}
}

//---------------------------------------------------------------------------------
// GetMinimalRankedVertex - Returns a minimally ranked vertex that is legal to add
// to the given group
// Parameters:
// Group* group - the group the vertex will be added to
// makeInterchangeableChecks - to check extra checks for interchangeable vertices
// or not
// Returns: A minimaly ranked vertex that is legal for group or NULL if none found
// Vertex is removed from graph but not added to group
//---------------------------------------------------------------------------------
Vertex* Graph::GetMinimalRankedVertex(Group* group, bool makeInterchangeableChecks)
{
	Vertex* vertex;
	
	ResetTempGroupIfNeeded(group);	

	if (m_Vertices.empty())
	{
		return NULL;
	}

	bool foundVertex = false;
	int counter = 0;

	while (!foundVertex && counter < m_RandomIterations)
	{
		counter++;

		RemoveEmptyRankSets();

		//  If there are no more vertices - stop with NULL
		if (m_Vertices.empty())
		{
			vertex = NULL;
			foundVertex = true;
			Debug::PrintDebugMsg("Graph is empty");

		} else
		{
			// Try to get a random vertex from the smallest rank available
			vertex = (m_Vertices.begin()->second)->GetRandomVertex();

			// Remove it from graph, it is legal or should go to the temp group
			if (group->IsLegalToAdd(vertex, makeInterchangeableChecks))
			{
				foundVertex = true;				
			}
			else
			{
				// Move the vertex to a temporary set so we won't choose it again for this group
				// The vertex will only be restored when we are done with the group.
				// We do not need to update vertex neighbours - it is still counted in the graph
				RemoveVertex(vertex);
				MoveVertexToTempSet(vertex);
			}
		}
	}

	if (vertex != NULL && foundVertex)
	{
		RemoveVertex(vertex);
	}

	if (!foundVertex || counter >= m_RandomIterations)
	{
		Debug::PrintDebugMsg("Max iterations for search passed");
		return NULL;
	}

	return vertex;
}

//---------------------------------------------------------------------------------
// RemoveVertex - Removes the vertex from the graph
// Parameters:
// vertex - vertex to remove
//---------------------------------------------------------------------------------
void Graph::RemoveVertex(Vertex* vertex)
{
	if (!vertex->IsInGraph())
	{
		RemoveVertexByName(vertex);
		vertex->ResetContainer();
		return;
	}

	if (this != vertex->GetContainingGraph())
		{
			Debug::PrintDebugMsg("Vertex "+vertex->PrintName()+" isn't in this graph");
			RemoveVertexByName(vertex);
			vertex->ResetContainer();
			return;
		}

	// Try to get the vertex's RankSet from the pointer
	RankSet *currentRankSet = dynamic_cast<RankSet*>(vertex->GetContainer());
	
	// If vertex has not rank, it might be in temp group
	if (currentRankSet==NULL)
	{
		// Check if vertex is in temp group
		TempVertexContainer *tempSet = static_cast<TempVertexContainer*>(vertex->GetContainer());
		if (tempSet == NULL)
		{
			if (IsVertexInGraph(vertex))
			{
				throw new GraphColoringException("Vertex "+vertex->PrintName()+" to remove is in the graph but container is stale");
			} 
			else
			{
				throw (new GraphColoringException("Vertex "+vertex->PrintName()+" to remove is not in graph"));
			}
		} 

		m_TempContainer->RemoveVertex(vertex);
	} else
	{
		if (currentRankSet->GetRank() != vertex->Rank())
		{
			RemoveVertexByName(vertex);
			vertex->ResetContainer();
			return;
		}
		
		currentRankSet->RemoveVertex(vertex);				
	}	

	// Update the vertex is it nowhere (will updates neighbours' ranks)
	vertex->ResetContainer();
	// Update all neighbours that the vertex is not in the graph
	UpdateAllNeighbours(vertex);

}

//---------------------------------------------------------------------------------
// RemoveVertex - Removes the vertex from the graph
//---------------------------------------------------------------------------------
void Graph::RemoveVertexBase(VertexBase* vertexBase)
{
	Vertex *vertex = dynamic_cast<Vertex*>(vertexBase);
	if (vertex == NULL)
	{
		// if this isn't a vertex, this is a vertex set
		VertexSet *vertexSet = dynamic_cast<VertexSet*>(vertexBase);
		RemoveVertexSet(vertexSet);
		return;
	}
	else
	{
		RemoveVertex(vertex);
	}
}
//---------------------------------------------------------------------------------
// RemoveVertexByName - Removes the vertex from the graph, searches by name and not
// pointers
// Parameters:
// vertex - vertex to remove
//---------------------------------------------------------------------------------
void Graph::RemoveVertexByName(Vertex *vertex)
{

	// First try temp set
	set<Vertex*>::iterator it = m_TempContainer->Find(vertex);
	if (it != m_TempContainer->End())
	{
		m_TempContainer->Erase(it);
		UpdateAllNeighbours(vertex);
		return;
	}

	// Go over all the ranksets and look for vertex
	GraphVerticesIterator iter;
	for (iter = m_Vertices.begin(); iter != m_Vertices.end(); iter++)
	{
		RankSet *currentRankSet = iter->second;

		if (currentRankSet->ContainsVertex(vertex))
		{
			currentRankSet->RemoveVertex(vertex);
			UpdateAllNeighbours(vertex);
			return;
		}
	}

	throw new GraphColoringException("Trying to remove vertex that isn't in graph from graph");
}

//---------------------------------------------------------------------------------
// RemoveVertexSet - Removes both vertices from the graph
// Parameters:
// vertexSet - vertices to remove
//---------------------------------------------------------------------------------
void Graph::RemoveVertexSet(VertexSet *vertexSet)
{
	set<Vertex*>::iterator it;
	this->RemoveVertex(vertexSet->Vertex1());
	this->RemoveVertex(vertexSet->Vertex2());
}

//---------------------------------------------------------------------------------
// GetMinimalRankedVertexCouple: returns a minimally ranked vertex set (after limited
// search iterations that is legal to add to group)
// Is used to find vertex couples but can return sets containing more then 2 vertices
// Returns in vertexSet the set of vertices, or returns NULL in vertexSet
//---------------------------------------------------------------------------------
VertexSet* Graph::GetMinimalRankedVertexCouple(Group* group, bool makeInterchangeableChecks)
{
	ResetTempGroupIfNeeded(group);
	
	VertexSet *vertexSet = NULL;
	pair<Vertex*, Vertex*> vertexCouple;
	vertexCouple.first = vertexCouple.second = NULL;
	int counter = 0;
	
	if (CountWithoutTempSet() < 2)
	{
		Debug::PrintDebugMsg("No more vertices");
		// return an empty set of vertices
		try
		{
			return new VertexSet(m_Directory);
		}
		catch(std::bad_alloc *e)
		{
			e = NULL;
			return NULL;
		}
	}
	
	bool foundCouple = false;
	// Go on while we haven't found a legal couple, have at least 2 vertices in graph
	// and haven't passed max iterations
	while (!foundCouple && CountWithoutTempSet() >= 2 && counter < m_RandomIterations)
	{
		counter++;
		// Get couple (remove it temporarily from the graph) - if NULL,NULL is returned - 
		// no such couple exists
		VertexSet* tempVertexSet = GetVertexCoupleAfterMaxIterations(m_Directory);
		
		// if no such couple exists - return NULL,NULL
		if (tempVertexSet->Vertex1() == NULL)
		{
		    continue;
		} 	

		if (group->IsLegalToAdd(tempVertexSet, makeInterchangeableChecks))
		{
			// Found a couple
			foundCouple = true;
			// Remove vertices from graph - they are being returned
			RemoveVertex(tempVertexSet->Vertex1());
			RemoveVertex(tempVertexSet->Vertex2());
			vertexSet = tempVertexSet;
		} else
		{
			// Put vertices in temp group if they are illegal or in graph if we can choose them again
			// This will return them to the graph, in any case
			if (!(group->IsLegalToAdd(tempVertexSet->Vertex1())))
			{
				RemoveVertex(tempVertexSet->Vertex1());
				MoveVertexToTempSet(tempVertexSet->Vertex1());
			}

			if (!(group->IsLegalToAdd(tempVertexSet->Vertex2())))
			{
				RemoveVertex(tempVertexSet->Vertex2());
				MoveVertexToTempSet(tempVertexSet->Vertex2());				
			}
		}
	}

	if (counter >= m_RandomIterations)
	{
		Debug::PrintDebugMsg("Out of iterations");
	}

	if (CountWithoutTempSet() < 2)
	{
		Debug::PrintDebugMsg("Less than 2 vertices");
	}

	if (vertexSet != NULL)
	{
		Debug::PrintDebugMsg("Returning " + vertexSet->PrintName());
	} else
	{
		Debug::PrintDebugMsg("Returning NULL");
	}
	return vertexSet;
}


//---------------------------------------------------------------------------------
// InsertVertex: Adds a vertex to the graph and sets its container to the right
// RankSet.
// Parameters:
// Vertex* vertex - vertex to add
//---------------------------------------------------------------------------------
void Graph::InsertVertex(Vertex* vertex, bool updateNeighbours)
{
	if (updateNeighbours && IsVertexInGraph(vertex))
	{
		Debug::PrintDebugMsg(vertex->PrintName() + " is already in graph");
		if (vertex->GetContainingGraph() == this || vertex->GetContainingGraph() == NULL)
		{
			Debug::PrintDebugMsg(vertex->PrintName() + " is in this graph (or thinks it is in no graph");
			if (vertex->GetContainingGraph() == NULL)
			{
				Debug::PrintDebugMsg("in no graph");
			}
			RemoveVertex(vertex);
		}		
	}

	RankSet* correctSet;
	// Find rankset by rank
	map<long,RankSet*>::iterator it = m_Vertices.find(vertex->Rank()); 
	if (it == m_Vertices.end())
	{
		// Rank not found
		try
		{
			correctSet = new RankSet(this, vertex->Rank());
		}
		catch(std::bad_alloc *e) //memory allocation failed
		{
			e = NULL;
			Logger::LogMessage("ERROR: memory allocation failed in Graph::InsertVertex. vertex wasn't added to the graph.");
			return;
		}
		m_Vertices[vertex->Rank()] = correctSet;
	}
	correctSet = m_Vertices[vertex->Rank()];
	// find the RIGHT vertex reference associated with this graph
	Vertex* vertex1 = VertexDirectory::GetVertexFromDirectory(vertex->Name(), m_Directory);
	vertex1->Copy(vertex);
	correctSet->InsertNewVertex(vertex1);
	if (updateNeighbours)
	{
		UpdateAllNeighbours(vertex1);
	}
}

//---------------------------------------------------------------------------------
// InsertVertexSet: Adds a vertex set to the graph 
// Parameters:
// Vertex* vertex - vertex to add
//---------------------------------------------------------------------------------
void Graph::InsertVertexSet(VertexSet* vertexSet, bool updateNeighbours)
{
	InsertVertex(vertexSet->Vertex1(), updateNeighbours);
	InsertVertex(vertexSet->Vertex2(), updateNeighbours);
}

//---------------------------------------------------------------------------------
// InsertVertexBase: Checks if vertex is a vertex or vertex set and inserts it
//---------------------------------------------------------------------------------
void Graph::InsertVertexBase(VertexBase* vertexBase, bool updateNeighbours)
{
	Vertex *vertex = dynamic_cast<Vertex*>(vertexBase);
	if (vertex == NULL)
	{
		// if this isn't a vertex, this is a vertex set
		VertexSet *vertexSet = dynamic_cast<VertexSet*>(vertexBase);
		InsertVertexSet(vertexSet);
		return;
	}
	else
	{
		InsertVertex(vertex);
	}
}

//---------------------------------------------------------------------------------
// AddGroup: Add a whole group of vertices to the graph
// Paramters:
// Group - the group to add
//---------------------------------------------------------------------------------
void Graph::AddGroup(Group& group)
{
	for (list<Vertex*>::iterator it = group.Iterator(); !group.End(it); it++)
	{	
		AddVertexFromGroupOrList((*it));		
	}
}

//---------------------------------------------------------------------------------
// AddVertices: Add a whole list of vertices to the graph
// Paramters:
// verytices - the vertices to add
//---------------------------------------------------------------------------------
void Graph::AddVertices(list<Vertex*> vertices)
{
	char buffer[10];
	_itoa_s(vertices.size(),buffer,10,10);
	string message = "Adding ";
	message.append(buffer);
	message.append(" vertices to graph");
	Debug::PrintDebugMsg(message);
	int counter = 0;
	for (list<Vertex*>::iterator it = vertices.begin(); it != vertices.end(); it++)
	{	
		AddVertexFromGroupOrList((*it));		
		counter++;
		if (counter % 50 == 0)
		{
			memset(buffer,0,10);
			_itoa_s(counter,buffer,10,10);
			string msg = "Added ";
			msg.append(buffer);
			msg.append(" vertices");
			Debug::PrintDebugMsg(msg);
		}
	}
}

//---------------------------------------------------------------------------------
// AddRankSet: Add an entire RankSet to graph
// Parameters:
// rankSet - rankset to add
//---------------------------------------------------------------------------------
void Graph::AddRankSet(RankSet *rankSet)
{
	m_Vertices[rankSet->GetRank()] = rankSet;
}


//---------------------------------------------------------------------------------
// Clone: Deep copy
// Returns: a copy of the graph
//---------------------------------------------------------------------------------
Graph* Graph::Clone() 
{
	return Graph::CloneFromDirectory(NULL);	
}

//---------------------------------------------------------------------------------
// CloneFromDirectory: Deep copy
// Returns: a copy of the graph, vertices pointers taken from the supplied directory
//          if directory is NULL, uses current vertex pointers.
//---------------------------------------------------------------------------------
Graph* Graph::CloneFromDirectory(VertexDirectory* dir) 
{
	Graph* newGraph = NULL;
	try
	{
		newGraph = new Graph(m_MaxVertexCouplesForMininalRankSearch, m_RandomIterations, dir);
	}
	catch(std::bad_alloc *e) //memory allocation failed
	{
		e=NULL;
		Logger::LogMessage("memory allocation failed in Graph::CloneFromDirectory. graph wasn't created.");
		return NULL;
	}
	map<long, RankSet*>::const_iterator it;
	ReturnTempSetToGraph();
	for (it=m_Vertices.begin() ; it != m_Vertices.end(); it++ )
	{
		RankSet *currentSet = it->second;
		currentSet->InsertAllVerticesToNewGraph(newGraph);		
	}

	// No need to copy temp container - we returned it to the graph
	TempVertexContainer *tempContainerCopy = NULL;
	try
	{
		tempContainerCopy = new TempVertexContainer(newGraph);
	}
	catch(std::bad_alloc *e) //memory allocation failed
	{
		e = NULL;
		Logger::LogMessage("memory allocation failed in Graph::CloneFromDirectory. graph wasn't created.");
		delete newGraph;
		return NULL;
	}
	newGraph->SetTempContainer(tempContainerCopy);

	return newGraph;
}

//---------------------------------------------------------------------------------
// Count: Returns vertex total
//---------------------------------------------------------------------------------
int Graph::Count()
{
	int total = CountWithoutTempSet();
	total += m_TempContainer->Count();

	return total;
}

//---------------------------------------------------------------------------------
// IsVertexInGraph: returs true if vertex is in graph 
//---------------------------------------------------------------------------------
bool Graph::IsVertexInGraph(Vertex *vertex)
{
	
	// Look for the vertex in the temp set
	set<Vertex*>::iterator it = m_TempContainer->Find(vertex);
	if (it != m_TempContainer->End())
	{
		// Vertex is in the temp container
		return true;
	} else
	{
		// Go over all the ranksets and look for vertex
		GraphVerticesIterator iter;
		for (iter = m_Vertices.begin(); iter != m_Vertices.end(); iter++)
		{
			RankSet *currentRankSet = iter->second;

			if (currentRankSet->ContainsVertex(vertex))
			{
				return true;
			}
		}

		return false;
	}

}
	

//---------------------------------------------------------------------------------
// SetTempContainer: Updates temp container pointer (for clone)
//---------------------------------------------------------------------------------
void Graph::SetTempContainer(TempVertexContainer *copy)
{
	m_TempContainer = copy;
}

//---------------------------------------------------------------------------------
// GetVertexDirectory: returns the VertexDirectory instance associated with this
// graph. If no such Directory exosts, returns NULL
//---------------------------------------------------------------------------------
VertexDirectory* Graph::GetVertexDirectory()
{
	return m_Directory;
}

//-----------------------------------------------------------------------------
// RemoveGroupVerticesFromGraph
// Removes all the vertices in the group from the graph, if they are in it
//-----------------------------------------------------------------------------
void Graph::RemoveGroupVerticesFromGraph(Group* group)
{
	list<Vertex*>::iterator it;
	for (it = group->Iterator(); group->End(it) == false; it++)
	{
		if (IsVertexInGraph(*it) == true)
		{
			// We have to look by name since the vertex was used in a temp graph and pointers might not 
			// be relevant
			Vertex* vertex;
			VertexDirectory* dir = m_Directory;
			if (dir == NULL)
			{	//use static directory
				vertex = VertexDirectory::GetStaticCopyVertex((*it)->Name());
			}
			else
			{	// use the vertex directory associated with this graph
				vertex = dir->GetWorkingCopyVertex((*it)->Name());
			}
			RemoveVertexByName(vertex);
		}
	}
}

//---------------------------------------------------------------------------------
// MoveVertexToTempSet: Saves a vertex in the temp set and clears its container 
//---------------------------------------------------------------------------------
void Graph::FindVertexSetReplacements(VertexSet *vertexSet)
{	
	Group *group = dynamic_cast<Group*>(vertexSet->GetCurrentContainer());
	set<VertexKey>::iterator it;
	if (group == NULL)
	{
		throw new GraphColoringException("Vertex set is not in group");
	}
	// Remove vertex from its current group so we can check if it is legal to replace it
	group->RemoveVertexSet(vertexSet);
	
	// Go over sets at random and look for replacements
	for (int counter = 0; counter < m_MaxVertexCouplesForMininalRankSearch; counter++)
	{
		// Get 2 vertices 
		Vertex* v1 = GetRandomVertex();
		Vertex* v2 = GetRandomVertex();

		// If any is NULL, we ran out of vertices so we return NULL,NULL
		if (v1 == NULL || v2 == NULL)
		{
			Debug::PrintDebugMsg("No more random vertices, stop");
			break;
		}

		// if we have 2 vertices, make sure they are not neighbours, If they are neighbours, look 
		// for a different pair
		if (v1 == v2 || v1->Neighbours(v2))
		{
			continue;
		}	

		if (v1->GetContainingVertexSet() != NULL || v2->GetContainingVertexSet() != NULL)
		{
			continue;
		}

		if (vertexSet->Neighbours(v1) || vertexSet->Neighbours(v2))
		{
			continue;
		}

		VertexSet *newSet = NULL;
		try
		{
			newSet = new VertexSet(v1,v2);
		}
		catch (std::bad_alloc *e)
		{
			e = NULL;
			Logger::LogMessage("failed to create a VertexSet in FindVertexSetReplacements");
			throw new GraphColoringException("memory allocation failed");
		}
		
		if (!newSet->HasNeighbourInGroup(group))
		{	
			Debug::PrintDebugMsg("Found replacement!");
			// Return vertex to current group
			group->InsertNewVertexCouple(vertexSet);
			VertexSet::CreateInterchangeableLink(vertexSet,newSet);
			// Remove vertex from its current group so we can check if it is legal to replace it
			group->RemoveVertexSet(vertexSet);

			// Insert to vertex directory
			VertexDirectory::AddVertexSet(vertexSet);
			VertexDirectory::AddVertexSet(newSet);
		} 
		else
		{
			delete newSet;
		}	
	}
	

	// Return vertex to current group
	group->InsertNewVertexCouple(vertexSet);
	
}

//---------------------------------------------------------------------------------
// Private
//---------------------------------------------------------------------------------

//---------------------------------------------------------------------------------
// MoveVertexToTempSet: Saves a vertex in the temp set and clears its container 
// pointer
//---------------------------------------------------------------------------------
void Graph::MoveVertexToTempSet(Vertex* vertex)
{
	m_TempContainer->InsertNewVertex(vertex);	
}

//---------------------------------------------------------------------------------
// ReturnTempSetToGraph: Returns all the vertices in the temp set to their rankSets
//---------------------------------------------------------------------------------
void Graph::ReturnTempSetToGraph()
{
	// Go over all vertices in temp group, return them to graph by their rank
	// which is updated since we keep updating it
	set<Vertex*>::iterator it = m_TempContainer->Begin();
	
	while (it != m_TempContainer->End())
	{
		// Do not change neighbours rank - they were still counted in graph and didn't change it
		InsertVertex(*it, false);
		it++;
	}
	
	// Reset the group
	m_TempContainer->Clear();
}

//---------------------------------------------------------------------------------
// UpdateVertexRank: Updates a vertex's rank and its rank set to match
//---------------------------------------------------------------------------------
void Graph::UpdateVertexRank(Vertex* vertex) 
// Update vertex's rank by updateModifier (can be +-), update the vertex map
{
	// Try to get the vertex's RankSet from the pointer
	RankSet *currentRankSet = dynamic_cast<RankSet*>(vertex->GetContainer());
	
	// If the conversion was successful, move to the new group
	// If rankSet is null - it is in the temp group and we don't move it
	if (currentRankSet!=NULL) 
	{
		currentRankSet->RemoveVertex(vertex);
		// This will insert the vertex according to new rank
		InsertVertex(vertex, false);
	}
}

//---------------------------------------------------------------------------------
// RemoveEmptyRankSets: Clears the empty ranksets in the beginning of m_Vertices
//---------------------------------------------------------------------------------
void Graph::RemoveEmptyRankSets()
{
	while ((!m_Vertices.empty()) && (m_Vertices.begin()->second->IsEmpty())) 
	{
		m_Vertices.erase(m_Vertices.begin());
	}
}

//---------------------------------------------------------------------------------
// ResetTempGroupIfNeeded: Checks if we are dealing with a new group and resets 
// temp group if needed (returns it to graph)
//---------------------------------------------------------------------------------
void Graph::ResetTempGroupIfNeeded(Group* group)
{
	if (group != m_TempContainer->GetCurrentGroup())
	{
		// If we changed groups, we need to reset the temp group
		// It might be relevant to the new group
		ReturnTempSetToGraph();
		m_TempContainer->SetCurrentGroup(group);
	}
}

//--------------------------------------------------------------------------------- 
// GetMaxRank: Return maximal rank in graph
//--------------------------------------------------------------------------------- 
int Graph::GetMaxRank()
{
	GraphVerticesIterator it;
	int maxRank = 0;
	for (it = m_Vertices.begin(); it != m_Vertices.end(); it++)
	{
		if (it->first > maxRank)
		{
			maxRank = it->first;
		}
	}

	return maxRank;
}

//--------------------------------------------------------------------------------- 
// GetRandomVertex: Gets a random vertex from the graph (removes from graph)
// Returns NULL if none available
//---------------------------------------------------------------------------------
Vertex *Graph::GetRandomVertex()
{
	Vertex *vertex = NULL;
	while (vertex == NULL && !m_Vertices.empty())
	{
		int maxRank = GetMaxRank();
		int randomRank = rand() % (maxRank+1);
		GraphVerticesIterator it = m_Vertices.lower_bound(randomRank);
		RankSet *rankSet = it->second;
		if (rankSet->IsEmpty())
		{
			// Erase the empty rank set, try to find another random rank
			m_Vertices.erase(it);
		} else
		{
			// Get a vertex. It won't be NULL since the rankset isn't empty
			vertex = rankSet->GetRandomVertex();
		}
	}

	return vertex;
}

//--------------------------------------------------------------------------------- 
// CountWithoutTempSet: Returns the number of vertices that can be chosen for
// the current group
//--------------------------------------------------------------------------------- 
int Graph::CountWithoutTempSet()
{
	int total = 0;
	map<long,RankSet*>::iterator it = m_Vertices.begin();
	for (; it != m_Vertices.end(); it++)
	{
		total += (it->second)->Count();
	}
	return total;
}

//--------------------------------------------------------------------------------- 
// GetStaticCopyVertexCoupleAfterMaxIterations: Runs maximum iterations to find a minimally
// ranked couple to try to insert to group
//--------------------------------------------------------------------------------- 
VertexSet* Graph::GetVertexCoupleAfterMaxIterations(VertexDirectory *dir)
{
	pair<Vertex*, Vertex*> couple;
	couple.first = NULL;
	couple.second = NULL;

	// minCombinedRank is initialized to max - all vertices in graph
	int minCombinedRank = Count();

	for (int counter = 0; counter < m_MaxVertexCouplesForMininalRankSearch && CountWithoutTempSet() >= 2; counter++)
	{
		// Get 2 vertices 
		Vertex* v1 = GetRandomVertex();
		Vertex* v2 = GetRandomVertex();

		// If any is NULL, we ran out of vertices so we return NULL,NULL
		if (v1 == NULL || v2 == NULL)
		{
			Debug::PrintDebugMsg("Got NULL as random vertex, stopping");
			try
			{
				return new VertexSet(couple);
			}
			catch(std::bad_alloc *e)
			{
				e = NULL;
				Logger::LogMessage("failed to create a VertexSet in Graph::GetVertexCoupleAfterMaxIterations");
				throw(new GraphColoringException("memory allocation failed"));
			}
		}

		// if we have 2 vertices, make sure they are not neighbours, If they are neighbours, look 
		// for a different pair
		if (v1 == v2 || v1->Neighbours(v2))
		{
			continue;
		}

		int combinedRank = v1->GetCombinedRank(v2);
		if (combinedRank < minCombinedRank)
		{
			// Update couple and rank
			minCombinedRank = combinedRank;
			
			couple.first = v1;
			couple.second = v2;
		} 
	}

	try
	{
		return new VertexSet(couple);
	}
	catch(std::bad_alloc *e)
	{
		e = NULL;
		Logger::LogMessage("failed to create a VertexSet in Graph::GetVertexCoupleAfterMaxIterations");
		throw(new GraphColoringException("memory allocation failed"));
	}
}

//--------------------------------------------------------------------------------- 
// UpdateAllNeighbours: changes all neighbours rank by 1 in graph, moving them 
// to the right RankSet
//--------------------------------------------------------------------------------- 
void Graph::UpdateAllNeighbours(Vertex *vertex)
{
	// Decrease all neighbours rank in the graph by 1, this vertex is leaving the graph
	set<vector<bool>> neighboursInGraph = vertex->GetNeighboursInGraph();
	for (set<vector<bool>>::iterator it = neighboursInGraph.begin(); it != neighboursInGraph.end(); it++)
	{
		Vertex *neighbour;
		if (m_Directory == NULL)
		{
			neighbour = VertexDirectory::GetStaticCopyVertex(*it);
		}
		else
		{
			neighbour = m_Directory->GetWorkingCopyVertex(*it);
		}
		if (neighbour != NULL && neighbour->IsInGraph())
		{
			UpdateVertexRank(neighbour);
		}
		
	}
}

//--------------------------------------------------------------------------------- 
// AddVertexFromGroupOrList: helper method for the AddGroup and AddVertices methods.
// Re-adds vertex to the graph (if is in the graph - removes and then adds, 
// otherwize just adds it)
//--------------------------------------------------------------------------------- 
void Graph::AddVertexFromGroupOrList(Vertex *vertex)
{
	if (IsVertexInGraph(vertex))
	{
		// Remove vertex from the graph by its name, the pointer is not updated
		RemoveVertexByName(vertex);
	}
	InsertVertex(vertex, true);
}



